﻿// 0916train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>

using namespace std;

/*
 给定两个数组 A 和 B，若数组 A 的某个元素 A[i] 与数组 B 中的某个元素 B[j]
 满足 A[i]==B[j]，则寻找到一个匹配的二元组(i,j) ，
 请统计在这两个数组 A 和 B 中，一共存在多少个这样的二元组

输入描述
第一行输入数组 A 的长度 M ；
第一行输入数组 B 的长度 N ；
第三行输入数组 A 的值；
第四行输入数组 B 的值

输出描述
输出匹配的二元组个数

输入
5
4
1 2 3 4 5
4 3 2 1
输出
4

若下标从 0 开始，则匹配的二元组分别为(0,3)，(1,2)，(2,1)，(3,0)，共计 4 对二元组
 */
class Solution01
{
public:
    Solution01(vector<int>&vec_a, vector<int>&vec_b)
    {
        
        unordered_map<int, int>b_map;

        for (auto&num:vec_b)
        {
            b_map[num] += 1;
        }

        int result= 0;
        for (auto&num:vec_a)
        {
            if (b_map.count(num)>0)
            {
                result += b_map[num];
            }
        }

        cout << result;
	    //Solution01
    }
};


/*
 绘图机器的绘图笔初始位置在原点(0,0)机器启动后按照以下规则来进行绘制直线。
1. 尝试沿着横线坐标正向绘制直线直到给定的终点E
2. 期间可以通过指令在纵坐标轴方向进行偏移，
offsetY为正数表示正向偏移，
为负数表示负向偏移给定的横坐标终点值E以及若干条绘制指令，
请计算绘制的直线和横坐标轴以及x=E的直线组成的图形面积。

输入描述
- 首行为两个整数 N 和 E
- 表示有N条指令,机器运行的横坐标终点值E
- 接下来N行 每行两个整数表示一条绘制指令x offsetY
- 用例保证横坐标x以递增排序的方式出现
- 且不会出现相同横坐标x

取值范围
- 0<N<=10000
- 0<=x<=E<=20000
- -10000<=offsetY<=10000

输出描述
- 一个整数表示计算得到的面积 用例保证结果范围在0到4294967295之内。

示例1 输入输出 示例仅供调试，后台判题数据一般不包含示例
输入
4 10
1 1
2 1
3 1
4 -2
输出
12

横坐标终点值E 10

输入
2 4
0 1
2 -2
输出
4

 */
class Solution02
{
public:
    Solution02(vector<vector<int>>&num_vec, int end_pos)
    {
        vector<vector<int>>pos_vec;

        int v_size = num_vec.size();
        pos_vec.push_back(num_vec[0]);
        for (int i=1; i< v_size; i++)
        {
            vector<int>curr_item = num_vec[i];
            vector<int>pos_item(2);
            pos_item[0] = curr_item[0];
            pos_item[1] = curr_item[1] + pos_vec[i - 1][1];

            pos_vec.push_back(pos_item);
            //for
        }

        long long result = 0;
        int pos_vec_size = pos_vec.size();
        for (int i=1; i< pos_vec_size; i++)
        {
            int width = pos_vec[i][0] - pos_vec[i - 1][0];
            int height = abs(pos_vec[i - 1][1]);
            long long area = width * height;
            result += area;
        }
        vector<int>last_pos = pos_vec[pos_vec_size - 1];
        if (last_pos[0]< end_pos)
        {
            int width = end_pos - last_pos[0];
            int height = abs(last_pos[1]);
            long long area = width * height;
            result += area;
        }
        cout << result;

	    //Solution02
    }

};


/*
 MELON有一堆精美的雨花石(数量为n，重量各异)，准备送给S和W
 MELON希望送给俩人的雨花石重量一致，
 请你设计一个程序帮MELON确认是否能将雨花石平均分配

输入描述
第1行输入为雨花石个数：n，0 < n < 31.
第2行输入为空格分割的各雨花石重量：m[0] m[1] ... m[n - 1]，0 < m[k] < 1001
不需要考虑异常输入的情况

输出描述
如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等
如果不能均分，则输出-1

示例1：
输入
4
1 1 2 2
输出
2
说明
输入第一行代表共4颗雨花石，第二行代表4颗雨花石重量分别为1、1、2、2
均分时只能分别为1,2，需要拿出重量为1和2的两块雨花石，所以输出2

示例2：
输入
10
1 1 1 1 1 9 8 3 7 10
输出
3
说明
输入第一行代表共10颗雨花石，第二行代表10颗雨花石重量分别为1、1、1、1、1、9、8、3、7、10
均分时可以1,1,1,1,1,9,7和10,8,3，
也可以1,1,1,1,9,8和10,7,3,1，或者其他均分方式，
但第一种只需要拿出重量为10,8,3的3块雨花石，
第二种需要拿出4块，所以输出3(块数最少)。
 */
class Solution03
{
public:
    Solution03(vector<int>& num_vec)
    {
        
        int total_sum = 0;
        for (auto&num:num_vec)
        {
            total_sum += num;
        }

        if (total_sum%2!=0)
        {
            cout << -1;
            return;
        }

        int target_sum = total_sum / 2;

        int v_size = num_vec.size();
        vector<int>dynamic_vec(target_sum + 1, v_size);
        dynamic_vec[0] = 0;

        for (auto&curr:num_vec)
        {
            for (int sum = target_sum; sum >= 0; sum--)
            {
                if (sum - curr < 0) continue;

                dynamic_vec[sum] = min(dynamic_vec[sum - curr] + 1, dynamic_vec[sum]);
            }
        }

        if (dynamic_vec[target_sum]==v_size)
        {
            cout << -1;
            return;
        }
        
        cout << dynamic_vec[target_sum];
        //Solution03
    }
};

int main()
{
	{
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size;i++)
        {
            cin >> num_vec[i];
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
/*
4 10
1 1
2 1
3 1
4 -2
 */
        int v_size, end_pos;
        cin >> v_size >> end_pos;

        vector<vector<int>>num_vec(v_size);

        for (int i=0; i<v_size;i++)
        {
            vector<int>item(2);
            cin >> item[0] >> item[1];
            num_vec[i] = item;
        }

        Solution02 solu(num_vec, end_pos);
        return 0;
	}
    int a_size, b_size;
    cin >> a_size >> b_size;

    vector<int>a_vec(a_size);
    for (int i=0; i<a_size; i++)
    {
        cin >> a_vec[i];
    }

    vector<int>b_vec(b_size);
    for (int i=0; i<b_size; i++)
    {
        cin >> b_vec[i];
    }

    Solution01 solu(a_vec, b_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
